package Tree;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;

public class _508_MostFrequentSubtreeSum {
    Map<Integer, Integer> maps = new HashMap<Integer, Integer>();
    int count = 1;
    public int[] findFrequentTreeSum(TreeNode root) {
        ArrayList<Integer> res = new ArrayList<>();
        getSum(root);
        for (Map.Entry<Integer, Integer> entry : maps.entrySet()) {
//            System.out.println("map："+entry.getKey()+":"+entry.getValue());
            if (entry.getValue() == count) {
                res.add(entry.getKey());
            }
        }
        int[] ans = new int[res.size()];
        for (int i = 0; i < ans.length; i++) {
            ans[i] = res.get(i);
        }
        return ans;
    }

    public int getSum(TreeNode root) {
        if (root == null) {
            return 0;
        }
        //this step calculate the sum of left and right subtree,then calculate the root's sum
        int left = getSum(root.left);
        int right = getSum(root.right);
        int sum = root.val + left + right;
        if (maps.get(sum) == null) {
            maps.put(sum, 1);
        } else {
            int temp = maps.get(sum) + 1;
            if (temp > count) {
                count = temp;
            }
            maps.put(sum,temp);

        }
        return sum;
    }
}
